package lc.q1751_1800;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 给你一个 events 数组，其中 events[i] = [startDayi, endDayi, valuei] ，表示第 i 个会议在 startDayi 天开始，第 endDayi 天结束，如果你参加这个会议，你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。
 *
 * 你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。
 *
 * 请你返回能得到的会议价值 最大和 。
 */
public class Q1751 {

    public int maxValue(int[][] events, int k) {
        // 背包问题，设dp[i][j]为前i个会议里选的第j个的最大会议和
        // 那么递推公式则 dp[i][j] = max(dp[i-1][j], dp[p][j-1]+value[i]) p是指【1，start[i]】中有p个会议可参加
        Arrays.sort(events, Comparator.comparingInt(a -> a[1]));
        int n = events.length;
        int[][] dp = new int[n+1][k + 1];
        for (int i = 0; i < n; i++) {
            int p = lowerBound(events, events[i][0]);
            for (int j = 1; j <= k; j++) {
                dp[i+1][j] = Math.max(dp[i][j], dp[p][j-1] + events[i][2]);
            }
        }
        return dp[n][k];
    }

    private int lowerBound(int[][] events, int target) {
        // 这里是二分法，就是从所有events中能满足小于target最大的数量
        int left = 0, right = events.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (events[mid][1] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
